#include <stdio.h>
/*
 * 插入算法 insert sort 默认排序完是升序
 * 思想：
 *    默认局部有序，将后面的数插入到有序序列里面
 *
 *    1.第一个数，我们当成是有序的
 *    2.从第二个数开始，就要执行将数插入到局部有序序列这样的操作
 *        待插入值 value< 前面的值  就要继续往找，直到合适位置，然后插入
 *          如果 待插入值<前面的值，则前面的值需要要后移动一格，以腾出位置
 *          等找到 待插入值 > 局部序列里面的某一个值的时候，证明找到了合适位置，此时执行插入
 *       待插入值value > 前面局部有序序列里的最后的值 不用管
 *
 * */
void InsertSort(int *arr,int Len){
    //1.默认第一个数是有序的，作为有序序列，从第二个开始执行插入动作
    for (int i = 1; i <Len ; ++i) {
        //待插入的数 arr[i]
        //待比较的元素范围 [0,i-1]
        int value = arr[i];
        int j=i;
        while(value<arr[j-1]&&j>=1){
            arr[j]=arr[j-1];
            j--;
        }
        arr[j]=value;
    }
}
int main() {
    int arr[4]={3,1,4,2};
    int Len =4;
    InsertSort(arr,Len);
    //打印排序后的结果
    for (int i = 0; i < Len; ++i) {
        printf("%d ",arr[i]);
    }
   // printf("Hello, World!\n");
    return 0;
}
